/**
 * 双向链表, 顾名思义, 双向链表的结点中包含两个指针域, 分别是指向前驱和后继.
 * 
 * 相比与单链表, 双向链表访问元素更灵活
 */
#include <stdlib.h>
#include <stdio.h>
#include "./DoubleLinkedList.h"

/**
 * 双向链表的初始化, 
 * 带头结点
 */
Status InitList(DoubleLinkedList *list) {
    Node *headNode = (Node*)malloc(sizeof(Node));
    if(!headNode) {
        // 申请失败
        return ERROR;
    }
    // 1. 头节点的后继指针域指向NULL
    headNode->next = NULL;
    // 2. 头节点的前驱指针域指向NULL
    headNode->prev = NULL;
    // 3. 头指针指向头节点
    *list = headNode;
    return OK;
}

/**
 * 判断双向链表是否为空
 */
int ListIsEmpty(DoubleLinkedList list) {
    // 头节点的后继指针域是否指向NULL
    return list->next == NULL;
}

// 销毁链表
Status DestroyList(DoubleLinkedList *list) {
    Node *curNode = NULL;
    while(curNode = (*list)) {
        (*list) = curNode->next;
        free(curNode);
    }
    return OK;
}

// 获取链表长度
unsigned int ListLength(DoubleLinkedList list) {
    Node *curNode = list;
    unsigned int len = 0;
    while(curNode) {
        len++;
        curNode = curNode->next;
    }
    return len;
}

// 获取指定位置的元素, index可取范围是 1 - 链表的长度
Status GetElem(DoubleLinkedList list, int index, ElemType *e) {
    if(index < 1) {
        return ERROR;
    }
    Node *curNode = list->next;
    int curIdx = 1;
    while(curIdx < index && curNode) {
        curNode = curNode->next;
        curIdx++;
    }
    // 说明找到了最后, 还是没找到我想要的元素
    if(!curNode) {
        return ERROR;
    }
    // 到这一步说明curNode就是我要找的元素
    *e = curNode->data;
    return OK;
}

// 在指定的位置添加元素
Status InsertElem(DoubleLinkedList list, int index, ElemType e) {
    if(index < 1) {
        return ERROR;
    }
    Node *curNode = list;
    int curIdx = 0;
    // 要删除的下标是 1 至 list的长度+1
    while(curIdx < index-1 && curNode) {
        curNode = curNode->next;
        curIdx++;
    }
    // 说明找到了最后还是没找到
    if(!curNode) {
        return ERROR;
    }

    // 此时curNode就是要插入位置的前驱
    // 以下几步骤 重要
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = e;
    // 新节点的后继 指向 (要插入位置的前驱的后继)
    newNode->next = curNode->next;
    if(newNode->next) {
        newNode->next->prev = newNode;
    }
    newNode->prev = curNode;
    curNode->next = newNode;
    return OK;
}

// 在指定位置删除
Status DeleteElem(DoubleLinkedList list, int index, ElemType *e) {
    if(index <= 0) {
        return ERROR;
    }
    Node *curNode = list;
    int curIdx = 0;
    // 要删除的下标是 1 至 list的长度
    while(curNode && curIdx < index) {
        curNode = curNode->next;
        curIdx++;
    }

    if(!curNode) {
        return ERROR;
    }

    *e = curNode->data;
    curNode->prev->next = curNode->next;
    curNode->next->prev = curNode->prev;
    free(curNode);
    curNode = NULL;
    return OK;
}

int main() {
    DoubleLinkedList list;
    InitList(&list);
    printf("isempty: %d\n", ListIsEmpty(list));
    printf("ListLength: %d\n", ListLength(list));
    InsertElem(list, 1, 100);
    InsertElem(list, 2, 200);
    InsertElem(list, 2, 200);
    DestroyList(&list);
    return 0;
}